#pragma once
#include "TemplateVector.h"

template<typename DATA_TYPE>
struct GraphEdge;
//class GraphNode;
template<typename DATA_TYPE>
struct GraphNode
{
	TemplateVector<GraphEdge<DATA_TYPE>> connections;
	DATA_TYPE value; 
	//Adds a basic one-way connection to another node
	void addConnection(GraphNode<DATA_TYPE> * a_node)
	{
		GraphEdge<DATA_TYPE> connection = {a_node,this,0};
		connections.addNoDuplicates(connection);
	}
	void release()
	{
		connections.release();
	}
};

template<typename DATA_TYPE>
struct GraphEdge
{
	GraphNode<DATA_TYPE>* to;	//Node that this edge points to
	GraphNode<DATA_TYPE>* from; //Node that holds this edge
	float cost;					//Cost for transitioning between nodes if any
	bool operator==(const GraphEdge<DATA_TYPE>& a_data)
	{
		if(to == a_data.to && from == a_data.from && cost == a_data.cost)
			return true;
		else
			return false;
	}
};

template<typename DATA_TYPE>
class Graph
{
public:
	Graph(){}

	//Creates a new node and returns the pointer to it
	//! This doesn't connect the node to anything
	GraphNode<DATA_TYPE>* newNode(const DATA_TYPE& a_data)
	{
		GraphNode<DATA_TYPE> * m_node = new GraphNode<DATA_TYPE>;
		m_node->value = a_data;
		return m_node;
	}

	//Connects the "from" node to the "to" node
	void connectOneWay(GraphNode<DATA_TYPE> * from,GraphNode<DATA_TYPE>* to)
	{
		from->addConnection(to);
	}

	//Connects both nodes together in a two way relationship
	void connectTwoWay(GraphNode<DATA_TYPE> *a_node,GraphNode<DATA_TYPE>* b_node)
	{
		a_node->addConnection(b_node);
		b_node->addConnection(a_node);
	}

	//Creates and returns a list of nodes created from said list of DATA_TYPE
	TemplateVector<GraphNode<DATA_TYPE>*> & newNodeList(const TemplateVector<DATA_TYPE>& a_list)
	{
		TemplateVector<GraphNode<DATA_TYPE>*> returnList;
		int length = a_list.size();
		for (int i = 0; i < length; i++)
		{
			GraphNode<DATA_TYPE>* m_node = new GraphNode<DATA_TYPE>;
			m_node->value = a_list[i];
			returnList->add(m_node);
		}
		return returnList;
	}

	//Returns a TeamplateVector of GraphNode that were searched breadth first
	void BFS(GraphNode<DATA_TYPE> * a_node, TemplateVector<GraphNode<DATA_TYPE>*> & a_list)
	{
		a_list.addNoDuplicates(a_node);

		int length = a_node->connections.size();

		for (int i = 0; i < length; i++)
		{
			a_list.addNoDuplicates(a_node->connections[i].to);
		}
		for (int i = a_list.indexOf(a_node)+1; i < a_list.size(); i++)
		{
			BFS(a_list[i], a_list);
		}
	}

	//Returns a TeamplateVector of GraphNode that were searched depth first
	//Prefix not postfix
	void DFS(GraphNode<DATA_TYPE> * a_node, TemplateVector<GraphNode<DATA_TYPE>*> & a_list)
	{
		a_list.addNoDuplicates(a_node);
		int length = a_node->connections.size();
		for (int i = 0; i < length; i++)
		{
			if(a_list.indexOf(a_node->connections[i].to) == -1)
				DFS(a_node->connections[i].to, a_list);
		}
	}

	//Removes all links to the node
	//Needs a reference to all nodes that could possibly linked to them
	//! This does consume a lot of cycles, use sparcely
	void removeNode(GraphNode<DATA_TYPE>* a_node, TemplateVector<GraphNode<DATA_TYPE>*>& a_list)
	{
		int length = a_list.size();
		for (int i = 0; i < length; i++)
		{
			int len = a_list[i]->connections.size();
			for (int j = len-1; j >= 0; j--)
			{
				if (a_list[i]->connections[j].to == a_node)
				{
					a_list[i]->connections.remove(j);
				}
				else if (a_list[i]->connections[j].from == a_node)
				{
					a_list[i]->connections.remove(j);
				}
			}
		}
	}

	//Remove all links to all of the nodes in the list
	//Needs a reference to all nodes that could possible be linked to them
	//! This does consume a lot of cycles, use sparcely
	void removeNodeList(TemplateVector<GraphNode<DATA_TYPE>*>* a_nodes, TemplateVector<GraphNode<DATA_TYPE>*>& a_list)
	{
		int length = a_list.size();
		for (int i = 0; i < length; i++)
		{
			removeNode(a_nodes[i],a_list);
		}
	}


	//Returns a list of neighbors to the node
	void neighbors(GraphNode<DATA_TYPE>* a_node, TemplateVector<GraphNode<DATA_TYPE>*>& a_list)
	{
		int length = a_node->connections.size();
		for (int i = 0; i < length; i++)
		{
			a_list.add(a_node->connections[i].to);
		}
	}
};